# solution 1: normal recursion
# n: number of months
# k: number of offsprings
function fib1(n::Int, k::Int)
    if n <= 2
        return 1
    end
    return fib1(n - 1, k) + k * fib1(n - 2, k)
end
# test
for i in 1:10
    print("$(fib1(i,1)) ")
end
1 1 2 3 5 8 13 21 34 55

# solution 2: use memoization -> dynamic programming
# n: number of months
# k: number of offsprings

function fib2(n::Int, k::Int)
    memo = Dict{Int, Int}()
    memo[1] = 1
    memo[2] = 1
    return fib2(n, k, memo)
end

function fib2(n::Int, k::Int, memo::Dict{Int, Int})
    if haskey(memo, n)
        return memo[n]
    end
    memo[n] = fib2(n - 1, k, memo) + k * fib2(n - 2, k, memo)
    return memo[n]
end

# test
for i in 1:10
    print("$(fib2(i,1)) ")
end
1 1 2 3 5 8 13 21 34 55